import java.util.Stack;

public class LeetCode11_MaxVolumeWater {

    public static void main(String[] args) {
        System.out.println(maxArea(new int[]{1,8,6,2,5,4,8,3,7}));
    }

    public static int maxArea(int[] height) {
        int maxVolume = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int length = j - i;
                int width = Math.min(height[i], height[j]);
                maxVolume = Math.max(maxVolume, length * width);
            }
        }

        return maxVolume;
    }

    public int maxArea2(int[] height) {//利用单调性，先找一个小区间，找规律
        int left = 0;
        int right = height.length - 1;
        int maxVolume = 0;
        while (left < right) {
            int hei = Math.min(height[left], height[right]);
            int wide = right - left;
            maxVolume = Math.max(maxVolume, hei * wide);
            int num = height[left] >= height[right] ? right-- : left++;

        }

        return maxVolume;
    }
}
